package dynamicProgramming.SingleSequenceProblem;

/**
 * @author zxc
 * @date 2023/01/19 08:54
 **/

import java.util.Arrays;

/**
 *  题目 ：房屋偷盗问题
 *  题目详情 ：
 *  一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 *  如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *  给定一个代表每个房屋存放金额的非负整数数组 nums，请计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 *  1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 */
public class Rob_recursion {
    /**
     * 思路 ：带缓存的递归实现
     * （1）定义缓存数组redis，来保存（从标号0到标号i的房屋为止最多能够偷取到财物的最大值）
     * （2）获取到状态方程 ：f(i) = max(f(i - 1) , f(i - 2) + nums[i]);
     * 需要注意的是，该状态方程的隐性条件为i >= 2;
     * （3）由于nums数组中元素取值可能为0，即不能够通过redis元素 == 0，来判断其是否存储了（从标号0到标号i的房屋为止最多能够偷取到财物的最大值）
     * ===》 即，初始化redis数组时，将redis缓存数组中的所有元素都置为-1;
     * （4）返回值redis[nums.length - 1],即代表返回了从下标0到下标nums.length -1的房屋为止所能够偷盗财物的最大值;
     * 《====》 即，等价于redis[nums.length - 1]所存储的是当前n个房屋下，小偷所能够偷取的最大财物
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int length = nums.length;
        int[] redis = new int[length];
        // 由于nums数组中元素取值范围为[0 , 400],即导致redis缓存数组中所存储的元素可能为0;
        // 若是根据redis数组中元素为0，来进行判断当前redis[index]是否已经存储了（从标号0到标号i的房屋为止最多能够偷取到财物的最大值）
        Arrays.fill(redis , -1);
        recursionRedis(nums , length - 1 , redis);
        return redis[length - 1];
    }
    // 递归 ：实现获取从标号0到标号i的房屋为止最多能够偷取到财物的最大值 && 同时将其存储到redis缓存数组
    private void recursionRedis(int[] nums, int index, int[] redis) {
        if (index == 0){
            // 当index == 0，即小偷只能够进入0号房屋偷窃
            redis[index] = nums[0];
        }
        else if(index == 1){
            // 当index == 1，即小偷有两个选择（进入房屋0/1偷窃）
            redis[index] = Math.max(nums[0] , nums[1]);
        }
        // 若是下标index所对应的redis数组元素 < 0，即其未保存（从标号0到标号i的房屋为止最多能够偷取到财物的最大值）
        else if(redis[index] < 0){
            // 假设f(i)表示的是 从标号为0的房屋开始到标号为i的房屋为止最多能够偷取到的财物
            // 状态转移方程 ：f(i) = max(f(i - 1) , f(i - 2) + nums[i]);

            // 获取redis[index - 1];若是redis[index - 1] == 0的话，则会递归获取其值;若是其有值的直接返回即可;
            recursionRedis(nums , index - 1 , redis);
            // 获取redis[index - 2];若是redis[index - 2] == 0的话，则会递归获取其值;若是其有值的直接返回即可;
            recursionRedis(nums , index - 2 , redis);
            // 状态转移方程 ：要想求出redis[index]的值，即前提条件是需要知道redis[index - 1] && redis[index -2];
            redis[index] = Math.max(redis[index - 1] , redis[index - 2] + nums[index]);
        }
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：O（n）；
     * （2）空间复杂度 ：O（n）；（由于构建了辅助数组redis，大小与nums数组大小一致）
     */
}
